package leetcode_600;

/**
 *@author 周杨
 *RemoveBoxes_546_ 一个数组里有n中颜色元素 一个可以移除连续的k个相同的元素 并获得k*k个积分  求获得最大的积分值
 *describe:用三维数组动态规划做 dp[i][j][k]表示当[i,j]左边有k个与num[i]相同的元素  AC 71% 非常好的题目
 *2018年9月13日 上午10:08:27
 */
public class RemoveBoxes_546_ {
	public int removeBoxes(int[] boxes) {
	    int n = boxes.length;
	    int[][][] dp = new int[n][n][n];
	    return removeBoxesSub(boxes, 0, n - 1, 0, dp);
	}
	    
	private int removeBoxesSub(int[] boxes, int i, int j, int k, int[][][] dp) {
	    if (i > j) return 0;
	    if (dp[i][j][k] > 0) return dp[i][j][k];
	    
	    for (; i + 1 <= j && boxes[i + 1] == boxes[i]; i++, k++); // 目前k就是从i开始 连续相等的数目 i目前走到不连续位置
	    int res = (k + 1) * (k + 1) + removeBoxesSub(boxes, i + 1, j, 0, dp);//加入只移除所有最左边相等的盒子
	    
	    for (int m = i + 1; m <= j; m++) {
	        if (boxes[i] == boxes[m]) {//如果找到了这个盒子与左连续相同颜色的盒子 那么可以作为候选解
	            res = Math.max(res, removeBoxesSub(boxes, i + 1, m - 1, 0, dp) //那么就有两段解了
	            		+ removeBoxesSub(boxes, m, j, k + 1, dp));//此时k+1就是连接起来了两段区间
	        }
	    }
	        
	    dp[i][j][k] = res;
	    return res;
	}
}
